package com.lyj.sc.dynamicProgramming.test20220716;

import java.util.Map;

/**
 * @program: code-random
 * @description:有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
 * @author: lyj
 * @create: 2022-07-11 12:05
 * @version: 1.0
 * @Modifier By:
 **/
public class testweightbagproblem01 {
    public static void testweightbagproblem(int[] weight,int[] value,int bagsize){
            int wlen = weight.length;
            //1.定义dp二维数组
            int [][] dp = new int[wlen+1][bagsize+1];
            //2.初始化数组 背包为0
            for(int i=0;i<=wlen;i++){
                dp[i][0]=0;
            }
            //3.遍历循环 先遍历物品在遍历背包 Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
            for(int i =1;i<=wlen;i++){
                for(int j =1;j<=bagsize;j++){
                    if(weight[i-1]>j){
                        dp[i][j]=dp[i-1][j];
                    }else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i-1]] + value[i-1]);
                    }
                }
            }

            //打印结果
             for(int i =0;i<=wlen;i++){
                for(int j =0;j<=bagsize;j++){
                    System.out.println(dp[i][j]);
            }
        }
    }
    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }
}
